/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/sort-colors-ii
   @Language: C++
   @Datetime: 16-02-09 08:41
   */

// Method 1, HashMap, Time O(n), Space O(k), Time 268ms
class Solution{
public:
	/**
	 * @param colors: A list of integer
	 * @param k: An integer
	 * @return: nothing
	 */    
	void sortColors2(vector<int> &colors, int k) {
		// write your code here
		unordered_map<int,int> base;
		for(int i=colors.size(); i--; ++base[colors[i]]);
		for(int i=colors.size(); k; --k)
			for(; base[k]--; colors[--i]=k);
	}
};

// Method 2, Using prev-k elements to record each color count.
// Time O(n), Space O(1), Time 182ms
class Solution{
public:
	/**
	 * @param colors: A list of integer
	 * @param k: An integer
	 * @return: nothing
	 * Tip : use abs(A[k-1]) to record color k count.
	 */    
	void sortColors2(vector<int> &A, int k) {
		// write your code here
		for(int i=0, pos; i<A.size(); ++i){
			if (A[i]<=0) continue;	// not an element
			pos = A[i]-1;
			if (A[pos]>0){			// an element (color)
				A[i] = A[pos];		// find other element
				A[pos] = -1;
				--i;
			}
			else{					// color count, increase it
				--A[pos];
				A[i] = 0;
			}
		}
		for(int i=A.size(); k; --k)
			for(; A[k-1]<0; A[--i]=k)
				++A[k-1];
	}
};
